package com.zjsru.oneDay202210;

/**
 * @Author: CookLee
 * @Date: 2022/10/13
 * 最多能完成排序的块
 * 给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
 * 我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按[升序]排序后的原数组相同。
 *
 * 输入: arr = [4,3,2,1,0]
 * 输出: 1
 * 解释:
 * 将数组分成2块或者更多块，都无法得到所需的结果。
 * 例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
 *
 * 输入: arr = [1,0,2,3,4]
 * 输出: 4
 * 解释:
 * 我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
 * 然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
 */
public class MaxChunksToSorted {
    
    /**
     * 从0开始的数组
     */
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length, ans = 0;
        //i 定义为当前划分块的右边界下标,j 为当前划分块的左边界下标,定义 min 为当前划分块中元素最小值,定义 max 为当前划分块中元素最大值
        for (int i = 0, j = 0, min = n, max = 0; i < n; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
            //当且仅当 j=min 且 i=max 时，下标范围 [j,i] 排序结果为 [min,max]，此时块的个数加一，并重新初始化几个变量。
            if (j == min && i == max) {
                ans++;
                j = i + 1;
                min = n;
                max = -1;
            }
        }
        return ans;
    }
    
    /**
     * 贪心
     */
    public int maxChunksToSorted2(int[] arr) {
        int m = 0, res = 0;
        for (int i = 0; i < arr.length; i++) {
            m = Math.max(m, arr[i]);
            if (m == i) {
                res++;
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        MaxChunksToSorted maxChunksToSorted = new MaxChunksToSorted();
        int[] arr = new int[] {1, 0, 2, 3, 4};
        System.out.println(maxChunksToSorted.maxChunksToSorted(arr));
    }
}
